`
https://leetcode.cn/problems/maximum-subarray/
`

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  // dp 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
  const dp = new Array(nums.length).fill(0)
  dp[0] = nums[0]

  for (let i = 1; i < nums.length; i++) {
    // 要么和前面的最大子数组连一起，要么自己新开一个子数组
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
  }

  // 还需要遍历一遍才得到 nums 的最大子数组和
  return Math.max(...dp)
};